package leetcode.pre100;

import leetcode.pre50.Code31_NextPermutation_下一个全排列;

/**
 * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 * <p>
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * <p>
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 * <p>
 * 说明：
 * <p>
 * 给定 n 的范围是 [1, 9]。
 * 给定 k 的范围是[1,  n!]。
 * 示例 1:
 * <p>
 * 输入: n = 3, k = 3
 * 输出: "213"
 * 示例 2:
 * <p>
 * 输入: n = 4, k = 9
 * 输出: "2314"
 *
 * @date 2020/6/5 16:47
 */
public class Code60_GetPermutation_第K个全排列 {
    /**
     * TODO 获取下一个全排列:{@link leetcode.top100.Code31_NextPermutation}
     * TODO 获取第k个全排列, O(kn)
     * TODO 全排列：使用swap或者使用next全排列，时间复杂度O(n!)
     * TODO 字典序全排列：使用swap最后排序是O(n!log(n!))，使用nextO(n!)
     */
    public static String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        Code31_NextPermutation_下一个全排列 next = new Code31_NextPermutation_下一个全排列();
        for (int i = 0; i < k - 1; i++) {
            next.nextPermutation(nums);
        }
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(getPermutation(3, 3));
        System.out.println(getPermutation(4, 9));
    }
}
